In an indivisible participatory budgeting (PB) framework, we have a limited budget that is to be distributed among a set of projects, by aggregating the preferences of voters for the projects. All the prior work on indivisible PB assumes that each project has only one possible cost. In this work, we let each project have a set of permissible costs, each reflecting a possible degree of sophistication of the project. Each voter approves a range of costs for each project, by giving an upper and lower bound on the cost that she thinks the project deserves. The outcome of a PB rule selects a subset of projects and also specifies their corresponding costs. We study different utility notions and prove that the existing positive results when every project has exactly one permissible cost can also be extended to our framework where a project has several permissible costs. We also analyze the fixed parameter tractability of the problem. Finally, we propose some important and intuitive axioms and analyze their satisfiability by different PB rules. We conclude by making some crucial remarks.

Participatory budgeting (PB) has attracted much attention in recent times due to its wide applicability in social choice settings. In this paper, we consider indivisible PB which involves allocating an available, limited budget to a set of indivisible projects, each having a certain cost, based on the preferences of agents over projects. The specific, important, research gap that we address in this paper is to propose classes of rules for indivisible PB with weak rankings (i.e., weak ordinal preferences) and investigate their key algorithmic and axiomatic issues. We propose two classes of rules having distinct significance and motivation. The first is layered approval rules which enable weak rankings to be studied by carefully translating them into approval votes. The second is need-based rules which enable to capture fairness issues. Under layered approval rules, we study two natural families of rules: greedy-truncation rules and cost-worthy rules. The paper has two parts. In the first part, we investigate algorithmic and complexity related issues for the proposed rules. In the second part, we present a detailed axiomatic analysis of these rules, for which, we examine and generalize axioms in the literature and also introduce a new axiom, pro-affordability. The paper helps to highlight the trade-offs among practical appeal, computational complexity, and axiomatic compliance of these rules.

Approval-based multiwinner voting rules have recently received much attention in the Computational Social Choice literature. Such rules aggregate approval ballots and determine a winning committee of alternatives. To assess effectiveness, we propose to employ new noise models that are specifically tailored for approval votes and committees. These models take as input a ground truth committee and return random approval votes to be thought of as noisy estimates of the ground truth. A minimum robustness requirement for an approval-based multiwinner voting rule is to return the ground truth when applied to profiles with sufficiently many noisy votes. Our results indicate that approval-based multiwinner voting is always robust to reasonable noise. We further refine this finding by presenting a hierarchy of rules in terms of how robust to noise they are.